home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / mail / smail-3.1.28 / pd / pathalias / addlink.c next >
Encoding:
C/C++ Source or Header  |  1991-11-03  |  6.0 KB  |  292 lines
  1. /* Smail SCCS ID: @(#)pd/pathalias/addlink.c    1.2 11/4/91 00:43:11 */
  2.  
  3. /* pathalias -- by steve bellovin, as told to peter honeyman */
  4. #ifndef lint
  5. static char    *sccsid = "@(#)addlink.c    9.7 88/06/10";
  6. #endif /* lint */
  7.  
  8. #include "def.h"
  9.  
  10. /* exports */
  11. extern link *addlink();
  12. extern void deadlink(), atrace(), freelink();
  13. extern int tracelink(), maptrace();
  14. char *Netchars = "!:@%";    /* sparse, but sufficient */
  15. long Lcount;            /* how many edges? */
  16.  
  17. /* imports */
  18. extern int Tflag, Dflag;
  19. extern link *newlink();
  20. extern node *addnode();
  21. extern void yyerror(), die();
  22. #ifndef SMAIL_3
  23. extern int strcmp(), strlen();
  24. #endif
  25.  
  26. /* privates */
  27. STATIC void netbits(), ltrace(), ltrprint();
  28. static link    *Trace[NTRACE];
  29. static int    Tracecount;
  30.  
  31. #define EQ(n1, n2)    (strcmp((n1)->n_name, (n2)->n_name) == 0)
  32. #define LTRACE        if (Tflag) ltrace
  33.  
  34. link *
  35. addlink(from, to, cost, netchar, netdir)
  36.     node *from;
  37.     register node *to;
  38.     Cost cost;
  39.     char netchar, netdir;
  40. {    register link *l, *prev = 0;
  41.  
  42.     LTRACE(from, to, cost, netchar, netdir, "");
  43.     /*
  44.      * maintain uniqueness for dead links (only).
  45.      */
  46.     for (l = from->n_link; l; l = l->l_next) {
  47.         if (!DEADLINK(l))
  48.             break;
  49.         if (to == l->l_to) {
  50.             /* what the hell, use cheaper dead cost */
  51.             if (cost < l->l_cost) {
  52.                 l->l_cost = cost;
  53.                 netbits(l, netchar, netdir);
  54.             }
  55.             return l;
  56.         }
  57.         prev = l;
  58.     }
  59.     
  60.  
  61.     /* allocate and link in the new link struct */
  62.     l = newlink();
  63.     if (cost != INF)    /* ignore back links */
  64.         Lcount++;
  65.     if (prev) {
  66.         l->l_next = prev->l_next;
  67.         prev->l_next = l;
  68.     } else {
  69.         l->l_next = from->n_link;
  70.         from->n_link = l;
  71.     }
  72.  
  73.     l->l_to = to;
  74.     /* add penalty */
  75.     if ((l->l_cost = cost + from->n_cost) < 0) {
  76.         char buf[100];
  77.  
  78.         l->l_flag |= LDEAD;
  79.         sprintf(buf, "link to %s ignored with negative cost", to->n_name);
  80.         yyerror(buf);
  81.     }
  82.     if (netchar == 0) {
  83.         netchar = DEFNET;
  84.         netdir = DEFDIR;
  85.     }
  86.     netbits(l, netchar, netdir);
  87.     if (Dflag && ISADOMAIN(from))
  88.         l->l_flag |= LTERMINAL;
  89.  
  90.     return l;
  91. }
  92.  
  93. void
  94. deadlink(nleft, nright) 
  95.     node *nleft, *nright;
  96. {    link *l, *lhold = 0, *lprev, *lnext;
  97.  
  98.     /* DEAD host */
  99.     if (nright == 0) {
  100.         nleft->n_flag |= NDEAD;        /* DEAD host */
  101.         return;
  102.     }
  103.  
  104.     /* DEAD link */
  105.  
  106.     /* grab <nleft, nright> instances at head of nleft adjacency list */
  107.     while ((l = nleft->n_link) != 0 && l->l_to == nright) {
  108.         nleft->n_link = l->l_next;    /* disconnect */
  109.         l->l_next = lhold;        /* terminate */
  110.         lhold = l;            /* add to lhold */
  111.     }
  112.  
  113.     /* move remaining <nleft, nright> instances */
  114.     for (lprev = nleft->n_link; lprev && lprev->l_next; lprev = lprev->l_next) {
  115.         if (lprev->l_next->l_to == nright) {
  116.             l = lprev->l_next;
  117.             lprev->l_next = l->l_next;    /* disconnect */
  118.             l->l_next = lhold;        /* terminate */
  119.             lhold = l;
  120.         }
  121.     }
  122.  
  123.     /* check for emptiness */
  124.     if (lhold == 0) {
  125.         addlink(nleft, nright, INF / 2, DEFNET, DEFDIR)->l_flag |= LDEAD;
  126.         return;
  127.     }
  128.  
  129.     /* reinsert deleted edges as DEAD links */
  130.     for (l = lhold; l; l = lnext) {
  131.         lnext = l->l_next;
  132.         addlink(nleft, nright, l->l_cost, NETCHAR(l), NETDIR(l))->l_flag |= LDEAD;
  133.         freelink(l);
  134.     }
  135. }
  136.  
  137. STATIC void
  138. netbits(l, netchar, netdir)
  139.     register link *l;
  140.     char netchar, netdir;
  141. {
  142.     l->l_flag &= ~LDIR;
  143.     l->l_flag |= netdir;
  144.     l->l_netop = netchar;
  145. }
  146.  
  147. int
  148. tracelink(arg) 
  149.     char *arg;
  150. {    char *bang;
  151.     link *l;
  152.  
  153.     if (Tracecount >= NTRACE)
  154.         return -1;
  155.     l = newlink();
  156.     bang = index(arg, '!');
  157.     if (bang) {
  158.         *bang = 0;
  159.         l->l_to = addnode(bang+1);
  160.     } else 
  161.         l->l_to = 0;
  162.  
  163.     l->l_from = addnode(arg);
  164.     Trace[Tracecount++] = l;
  165.     return 0;
  166. }
  167.  
  168. /*
  169.  * the obvious choice for testing equality is to compare struct
  170.  * addresses, but that misses private nodes, so we use strcmp().
  171.  */
  172.  
  173. STATIC void
  174. ltrace(from, to, cost, netchar, netdir, message)
  175.     node *from, *to;
  176.     Cost cost;
  177.     char netchar, netdir, *message;
  178. {    link *l;
  179.     int i;
  180.  
  181.     for (i = 0; i < Tracecount; i++) {
  182.         l = Trace[i];
  183.         /* overkill, but you asked for it! */
  184.         if (l->l_to == 0) {
  185.             if (EQ(from, l->l_from) || EQ(to, l->l_from))
  186.                 break;
  187.         } else if (EQ(from, l->l_from) && EQ(to, l->l_to))
  188.             break;
  189.         else if (EQ(from, l->l_to) && EQ(to, l->l_from))
  190.             break;    /* potential dead backlink */
  191.     }
  192.     if (i < Tracecount)
  193.         ltrprint(from, to, cost, netchar, netdir, message);
  194. }
  195.  
  196. /* print a trace item */
  197. STATIC void
  198. ltrprint(from, to, cost, netchar, netdir, message)
  199.     node *from, *to;
  200.     Cost cost;
  201.     char netchar, netdir, *message;
  202. {    char buf[256], *bptr = buf;
  203.  
  204.     strcpy(bptr, from->n_name);
  205.     bptr += strlen(bptr);
  206.     *bptr++ = ' ';
  207.     if (netdir == LRIGHT)            /* @% */
  208.         *bptr++ = netchar;
  209.     strcpy(bptr, to->n_name);
  210.     bptr += strlen(bptr);
  211.     if (netdir == LLEFT)            /* !: */
  212.         *bptr++ = netchar;
  213.     sprintf(bptr, "(%ld) %s", cost, message);
  214.     yyerror(buf);
  215. }
  216.  
  217. void
  218. atrace(n1, n2)
  219.     node *n1, *n2;
  220. {    link *l;
  221.     int i;
  222.     char buf[256];
  223.  
  224.     for (i = 0; i < Tracecount; i++) {
  225.         l = Trace[i];
  226.         if (l->l_to == 0 && ((node *) l->l_from == n1 || (node *) l->l_from == n2)) {
  227.             sprintf(buf, "%s = %s", n1->n_name, n2->n_name);
  228.             yyerror(buf);
  229.             return;
  230.         }
  231.     }
  232. }
  233.  
  234. int
  235. maptrace(from, to)
  236.     register node *from, *to;
  237. {    register link *l;
  238.     register int i;
  239.  
  240.     for (i = 0; i < Tracecount; i++) {
  241.         l = Trace[i];
  242.         if (l->l_to == 0) {
  243.             if (EQ(from, l->l_from) || EQ(to, l->l_from))
  244.                 return 1;
  245.         } else if (EQ(from, l->l_from) && EQ(to, l->l_to))
  246.                 return 1;
  247.     }
  248.     return 0;
  249. }
  250.  
  251. void
  252. deletelink(from, to)
  253.     node *from;
  254.     node *to;
  255. {    register link *l, *lnext;
  256.  
  257.     l = from->n_link;
  258.  
  259.     /* delete all neighbors of from */
  260.     if (to == 0) {
  261.         while (l) {
  262.             LTRACE(from, l->l_to, l->l_cost, NETCHAR(l), NETDIR(l), "DELETED");
  263.             lnext = l->l_next;
  264.             freelink(l);
  265.             l = lnext;
  266.         }
  267.         from->n_link = 0;
  268.         return;
  269.     }
  270.  
  271.     /* delete from head of list */
  272.     while (l && EQ(to, l->l_to)) {
  273.         LTRACE(from, to, l->l_cost, NETCHAR(l), NETDIR(l), "DELETED");
  274.         lnext = l->l_next;
  275.         freelink(l);
  276.         l = from->n_link = lnext;
  277.     }
  278.  
  279.     /* delete from interior of list */
  280.     if (l == 0)
  281.         return;
  282.     for (lnext = l->l_next; lnext; lnext = l->l_next) {
  283.         if (EQ(to, lnext->l_to)) {
  284.             LTRACE(from, to, l->l_cost, NETCHAR(l), NETDIR(l), "DELETED");
  285.             l->l_next = lnext->l_next;
  286.             freelink(lnext);
  287.             /* continue processing this link */
  288.         } else
  289.             l = lnext;    /* next link */
  290.     }
  291. }
  292.